#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 1000

void shell_sort(int *p, int n);

int main(void)
{
	int i;
	int a[N];

	srand((int)time(NULL));

	for (i = 0; i < N; ++i)
	{
		a[i] = rand() % 10000;
	}

	shell_sort(a, N);

	for (i = 0; i < N; ++i)
		printf("%d ", a[i]);
	printf("\n");

	return 0;
}

void shell_sort(int *p, int n)
{
	int i, j, gap;
	int tmp;

	for (gap = n/2; gap != 0; gap /= 2)
	{
		for (i = gap; i < n; ++i)
		{
			tmp = p[i];
			for (j = i;j >= gap; j -= gap)
			{
				if (tmp < p[j - gap])
				{
					p[j] = p[j - gap];
				}
				else
				{
					break;
				}
			}
			p[j] = tmp;
		}
	}
}